1. Field of the Invention
The present invention generally relates to the calibration of digital printers, such as laser and ink jet printers, and, more particularly, to a method and apparatus for calibrating a printer, which method and apparatus do not depend on geometric assumptions on the printed dots.
2. Background Description
Most printers today can print in only a limited number of colors. Digital halftoning is a technique for printing a picture (or more generally displaying it on some two-dimensional medium) using small dots with a limited number of colors such that it appears to consist of many colors when viewed from a proper distance. For example, a picture of black and white dots can appear to contain grey levels when viewed from some distance. In fact the rest of the discussion will be restricted to the case of grayscale images and their rendering by black and white printers to facilitate the presentation. Anyone versed in the art of digital halftoning should know how to adapt the present invention to color images. When we speak of ink, it could mean any material and/or mechanism which produces the black in the image, i.e., it could be toner for a xerographic printer, ink for an inkjet printer, etc.
We will be concerned with bilevel, fixed pixel size printers (for instance laser printers). Such printers have two fundamental characteristics:
1) The print resolution, say d dpi (dots per inch), which can be interpreted as saying that the intended fundamental units of the print are arranged on a grid of squares with each square or pixel of size 1/d inches by 1/d inches, where d typically varies from about 300 to about 3000. In some cases, the pixels lie on a rectangular grid, but the discussion adapts equally well to this case, so we will always assume square pixels for definiteness. PA0 2) The dot gain which tells us how the actual printed pixel (or dot) differs from a perfect 1/d by 1/d square in shape and size (notice that in previous sentences, the word "dot" was used in a loose sense). While many printers perform differently, standard theory and much of the prior art on calibration assumes that printers print dots which can be reasonably described as round, say with diameter D (or as an ellipse in the case of a rectangular grid), and the dot gain is often described accordingly.
In the sequel, we make the assumption that no printed dot goes beyond a circle with diameter 2/d centered at the middle of the pixel where it is intended to be printed (a circular dot which covers an entire 1/d by 1/d square has diameter at least .sqroot.2/d). This assumption is made to simplify the discussion and in particular the description of the invention. Adaptation to a more general case is tedious to describe but not difficult to implement by anyone skilled in the art of digital printing.
In this invention, we are not concerned with modeling the properties of light, ink, paper and eye interactions. Such work has been done by Neugebauer, Murray-Davies, Yule-Nielsen, Clapper-Yule, BeerBouguer, Kubelka-Munk, and others as described in Henry Kang's book, Color Technology for Electronic Imaging Devices, SPIE Optical Engineering Press, 1997, which is incorporated herein by reference in its entirety. However, none of these models is concerned with the effect of neighboring pixels on the amount of ink deposited at a given pixel, which is the central contribution of the present invention. If the measurement tools which are used to implement the present invention measure the coverage of the ink on paper, these previous theories can be used to obtain the corresponding human visual response. Some other tools directly measure the human visual response, in which case the measurements can be used directly.
Consider now some grayscale image to be printed with a digital printer. We assume that the image is of size h by v, where h and v are expressed in inches to be consistent with the unit used in the dpi description. It is then convenient to interpret this image as a matrix I of size H=h.times.d by V=v.times.d in the following way:
One thinks of the image as covered by little squares of size 1d by 1/d (also called pixels). PA1 Then each pixel p can be designated by its horizontal ordering number i (say from left to right) and its vertical ordering number j (say from top to bottom). Thus, the location of p is specified by the pair (i,j). PA1 To the pixel at (i,j) one assigns the value g between "0" and "1", where "0" corresponds to white, "1" corresponds to black, and more generally, g corresponds to the grey level of this particular pixel. PA1 The matrix I is then defined by setting I.sub.(i,j) =g. PA1 either one includes a model for the dots in the digital halftoning algorithm like that disclosed in U.S. Pat. No. 5,473,439 to Pappas and Neuhoff, in which case the calibration of a printer amounts to getting some parameters of the model such as the radius of the dots for round dot models, or PA1 one conceives the algorithm for perfect square dots and then adapts it to any printer using some pure calibration method.
Given a matrix such as I, a digital halftoning algorithm will associate to it a H by V halftone matrix M whose entries M.sub.(i,j), are either "0" or "1". Now "0" means that no dot will be printed by the digital printer at pixel (i,j), while a "1" means that a dot is to be printed.
It is clear that the implementation of any halftoning algorithm has to take the dot gain into account; but more has to be said. The fact is that, besides dot gain, one of the problems to be solved by a digital halftoning method is that some types of printers do not necessarily print a dot at (i,j) each time M.sub.(i,J) =1. In particular, this is the case for laser printers. Usually, the likelihood of a dot being printed at (i,j) when M.sub.(i,j) =1 depends on whether nearby dots also have to be printed. The same physical mechanism which causes the unpredictability of a dot being printed usually also causes the shape of dots to depend on whether nearby dots are to be printed or not. In other words, the effective dot covering is not constant (and usually can vary from the classical printer specification in terms of dot gain). Accordingly, because of both dot gain effects and the unpredictability of printing dots intended to be printed, the dots may not exactly cover the corresponding pixels. Most often, they overlap portions of neighboring pixels (see FIG. 1B), or may just not cover anything. Clearly, some account has to be taken of this discrepancy.
There are currently two main ways to take account of the effective dot covering:
In some sense, the model based methods are microscopic in nature, but make strong, often unrealistic, assumptions about the printers to which one may apply them. The pure calibration methods are more empirical than the model based methods but have the disadvantage that they require testing each time one tries to implement a new algorithm. In fact, using prior art, preliminary calibration should precede any field test of any new algorithm if no model based consideration is used. This is obviously time consuming and one of the merits of the invention disclosed here is to avoid this loss of time, while using a more realistic model than in simple model-based techniques such as in U.S. Pat. No. 5,473,439.
A good digital halftoning algorithm should make sure that the ink that is actually put down is in accordance with what you want to print. This requires a proper method to calibrate, and we provide such a method. More precisely, this invention presents a new calibration method which can be used in a variety of halftoning methods, and is devised so that it can serve as a basis for a novel model based digital halftoning algorithm while keeping most of the pragmatic flavor of pure calibration methods. In some sense, the present invention allows one to perform the calibration so that it results in a realistic model for what will be actually printed at each pixel depending on the local configuration of dots intended to be printed.